/*
https://leetcode.cn/problems/number-of-provinces/description/
547. 省份数量
方钊堉 2024.10.13
并查集
*/

class Solution {
public:
    // 查找函数，用于查找根节点
    int findRoot(int node) {
        int root = node;
        while(set[root] != root) // 如果当前节点不是根节点，则向上查找
            root = set[root];
        return root;
    }

    // 合并两个节点所在的集合
    void unite(int node1, int node2) {
        int root1, root2;
        root1 = findRoot(node1); // 查找第一个节点的根节点
        root2 = findRoot(node2); // 查找第二个节点的根节点
        if(root1 != root2) // 如果两个节点不在同一个集合中，则合并它们
            set[root1] = root2;
    }

    int set[201] = {0}; // 初始化集合数组

    // 主函数，计算连通分量的数量
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size(); // 获取城市数量
        for(int i = 1; i <= n; i++){
            set[i] = i; // 初始化每个城市的父节点为自己
        }
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                if (isConnected[i][j]){ // 如果两城市直接相连
                    unite(i + 1, j + 1); // 合并这两个城市所在的集合
                }
            }
        }
        int count = 0; // 计数器，用于统计连通分量的数量
        for(int i = 1; i <= n; i++){
            if(set[i] == i) // 如果当前城市是其所在集合的根节点
                count++; // 连通分量数量加一
        }
        return count; // 返回连通分量的数量
    }
};